1. Field of the Invention
The present invention relates to the field of validating schematic and layout designs of circuits to determine that the components and connection points logically specified by the schematic design appear in the same sequence in the physical layout of traces in layers of silicon which are representative of the components.
2. Art Background
In the design of a circuit, such as an ASIC custom VLSI, a logic design (often referred to as the schematic) is first developed to identify the logic components required to provide the desired functionality. For example, the schematic will identify the component or device type (e.g., a pfet transistor) and the signals connected to the leads of the component. This is illustrated by FIGS. 1a-1f. FIG. 1a shows the logic interconnection of the logic components which comprise the circuit. The schematic provides for four components, 5,6,7,8 four input terminals in1, in2, in3, in4 and one output terminal out1. FIG. 1b illustrates the schematic for the components 5,6 comprising two pfet devices and two nfet devices. Inputs I1, I2 (21,22) correspond to inputs in1, in2 of component 6 in FIG. 1a. Similarly, inputs 11, 12 correspond to inputs in3, i4 of component 5 in FIG. 1a. FIG. 1c illustrates the schematic for component 7 of FIG. 1a and FIG. 1d illustrates the schematic of component 8 in FIG. 1a.
Once the logic design is complete, a layout is generated which physically specifies the logic components in one or more layers of silicon. The layout identifies the physical layout of signal paths to be and components to be created in the integrated circuit fabrication process. FIGS. 2a-2f is illustrative of a layout for the schematic of FIGS. 1a-1e. FIG. 2a illustrates the layout for the schematic of FIG. 1a. The layout consists of four devices, two corresponding to the snd02a component of FIG. 1b, one corresponding to the snr02a component of FIG. 1c and one corresponding to the sin00a component of FIG. 1d. FIGS. 2b, 2c and 2d respectively show an enlarged view of the layout for components snd02a, snr02a and sin00a. The layout for component snd02a, FIG. 2b, consists of two pfet devices and two nfet devices having input terminals i1, i2 and output terminals out, vss! and vcc!. The layout for component snr02a, FIG. 2c, consists of two pfet devices, two nfet devices, input terminals i1, i2 and output terminals out, vss!, vcc!. The layout for component sin00a, FIG. 2d, consists of one pfet device and one nfet device having one input terminal i1 and three output terminals, out, vss! and vcc!.
From the logic design, a net list can be generated. The net list is a list of interconnected locations which identify the signal paths to and from components in the circuit. This is illustrated in FIGS. 1e-1f.FIGS. 1e-1fprovide an illustrative net list for the schematic of FIG. 1a. Component snr02a corresponds to components 5,6 of FIG. 1a and the device of FIG. 1b. The net list identifies the input/output connections to the component, i1, i2 and out, the 2 nfet and 2 pfet devices and their input/output connections as well as the sizes of the devices (identified by the "w" before the dimensions). Similarly, the net list for snd02a, the component illustrated in FIG. 1c corresponding to the component 7 of FIG. 1a, and sin00a, the component illustrated in FIG. 1d and corresponding to component 8 of FIG. 1a are specified. The layout of FIG. 1a is defined in the net list by main circuit "patent2", input/output terminals in1, in2, in3, in4 and out1, and four instances of components; one instance of device snr02a, one instance of component sin00aand two instances (I1, I0) of component snd02a.
A second net list can be generated from the layout design. This is illustrated in FIGS. 2e-2f. FIGS. 2e-2f show the net list of the layout of FIG. 2a. Three block (also referred to as sub-circuit) net lists are defined, identifying the net lists for components sin00a, snr02a and snd02a. A main circuit net list identifies the instantiations of the blocks, one instantiation of sin00a (I3), one instantiation of snr02a (I2) and two instantiations of snd02a (I1, I0).
Although the layout design and schematic design represent the same circuit, the net lists for each may be quite different because the layout design may encompass multiple layers in which different portions of the same net of interconnected locations may reside in a plurality of smaller nets located on different layers. Single devices or components in the schematic might be represented by multiple parallel devices or components in the layout design. The layout net list for blocks might have different numbers of terminals to accommodate power and ground inputs as well as feed-thru holes to connect multiple layers in the layout design. For example, by visually comparing the net lists of FIGS.1e-1f and FIGS. 2e-2f it can be seen that the layout net list of FIGS. 2e-2f includes additional terminals (vcc!, vss!) not found in the net list of the schematic (FIGS. 1e-1f).
To verify that the layout design provides the components and logic specified in the logic design, the net list of the logic design is compared to the net list of the layout design. Typically the net list compare process is performed in a "flat" manner. A flat comparison is a device by device comparison of the logic net list to the layout net list where a device is a primitive that can be represented in terms of the drawn layers in the layout, e.g., an nfet is represented as an overlapping region between a poly layer and an n diffusion layer and a pfet is represented as an overlapping region between poly layer and p-diffusion layer. This procedure works well but is quite time consuming, computationally intensive and requires a large block of memory in order to execute on a computer. Many different techniques exist for performing the actual comparison of devices in the layout and schematic. One such technique is referred to as "Graph Isomorphism." For further information see, N. Kubo, I. Shirokawa, H. Ozaki, "A Fast algorithm for Testing Graph Isomorphism", Proceedings ISCAS Conference, pp. 641-644 (1979); C. Ebeling and 0. Zajicek, "Validating VLSI Circuit Layout by Wirelist Comparison" IEEE Int. Conference on CAD, pp. 172-173, September 1983; R. L. Spickelmier and A. R. Newton, "Wombat: A New Net list Comparison Program" IEEE Int. Conference on CAD, pp. 170-171, Sept. 1983; D. G. Corneil and D. G. Kirkpatrick, "A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem," SIAM Journal of Computing, vol. 9, no. 2, pp. 281-197, May 1980.
Designs prepared today are quite complex. Generally a design is prepared in hierarchical layers wherein subcircuits or blocks are defined to contain certain other devices blocks, ("sub-blocks") or components. For example, the circuit depicted in FIGS. 1a-1f and FIGS. 2a-2f is represented by 3 blocks sin00a, snd02a and snr02a. These blocks can then be utilized (i.e. instantiated) multiple times in the circuit.
A hierarchical design may include many hierarchical layers of blocks and components containing nested blocks. However, the hierarchies defined in a schematic design are not necessarily the same as hierarchies in the layout design. Furthermore, the identification of blocks may not be the same in the schematic and layout designs although they include the same components/devices. To compare a hierarchical design, the design is "flattened out" to the basic devices, replacing any blocks with the devices which comprise them. By flattening out the designs prior to comparison, the problems of inconsistent hierarchies and the names and compositions of the same are avoided. However, as stated above, designs have become more sophisticated and complex and the amount of computation time and memory needed to flatten out the design to individual devices and compare each occurrence of a device in the schematic design to a corresponding occurrence in the layout design have dramatically increased.
Furthermore, if any mismatches occur between the schematic and the layout circuits in a large and complex design, the mismatches are very difficult to fix and debug due to the size of the circuit after flattening. Typically it takes at least 4-5 iterations of circuit extraction and comparison before the layout design matches the schematic design. Thus it is not unusual for large designs to require 10-12 hours for each flat comparison. This is generally unacceptable.